#include "plan.h"

#include "minheap.h"
#include "stdbool.h"
#include "printf.h"
#include "stdlib.h"
// Edge gl_edges[] = {
//   {1,2,1},
//   {2,3,4},
//   {3,4,1},
//   {3,5,2},
//   {2,5,2},
//   {5,7,2},
//   {5,12,2},
//   {7,12,3},
//   {5,6,1},
//   {7,6,1},
//   {6,14,2},
//   {6,15,3},
//   {12,6,3},
//   {14,15,2},
//   {15,37,2},
//   {15,30,1},
//   {30,50,2},
//   {50,28,1},
//   {28,25,2},
//   {25,26,1},
//   {26,27,4},
//   {26,23,2},
//   {23,24,4},
//   {23,22,2},
//   {22,27,2},
//   {27,20,1},
//   {20,18,2},
//   {18,17,2},
//   {20,17,3},
//   {17,14,3},

//   };

static bool InsetEdge(Graph* G, const Edge* const E);
//static bool isFindInMap(int now, int next, int nNext);
bool isFindInGlobalMap(int now, int next, int nNext);
bool (*isFindInMap)(int now, int next, int nNext) = /*isFindInGlobalMap*/ NULL;//等于NULL表示不查找地图中是否有路段

/// @brief 创建图(邻接表表示)
/// @param edge 边数组
/// @param size 边的数量
/// @return 
Graph* createGraph(Edge edge[], int size) {
  // 分配内存空间,并初始化为0,其实这里也可以写成全局变量，因为这个比较大
  Graph* graph = (Graph*)calloc(1, sizeof(Graph));
  if (graph == NULL) {
    printf("内存分配失败\n");
    return NULL;
  }
  graph->ne = size;  // 边数
  // graph->nv = MAX_VERTEXES; // 顶点数
  //顶点数是指顶点的最大编号+1
  int vertexesNumMax = 0;
  for (int i = 0; i < graph->ne; i++) {
    /* -----找到顶点的最大编号-----*/
    if (edge[i].u > vertexesNumMax) {
      vertexesNumMax = edge[i].u;
    }
    if (edge[i].v > vertexesNumMax) {
      vertexesNumMax = edge[i].v;
    }

    /*------把边插入到邻接表中------*/
    // 插入正向边
    if (InsetEdge(graph, &edge[i]) == false) {
      printf("插入边的内存分配失败\n");
      // 释放之前已申请的内存
      deleteGraph(graph);
      return NULL;
    }
    // 插入反向边
    Edge e;
    e.u = edge[i].v;
    e.v = edge[i].u;
    e.weight = edge[i].weight;
    if (InsetEdge(graph, &e) == false) {
      printf("插入边的内存分配失败\n");
      // 释放之前已申请的内存
      deleteGraph(graph);
      return NULL;
    }
  }
  if(vertexesNumMax+1 > MAX_VERTEXES) {
    printf("顶点数超过最大值\n");
    deleteGraph(graph);
    return NULL;
  }
  graph->nv = vertexesNumMax + 1;
  return graph;
}

/// @brief 释放图和图上的顶点的邻接表的内存
/// @param G
void deleteGraph(Graph* G) {
  for (int i = 0; i < G->nv; i++) {
    AdjVNode* node = G->adjList[i].first;
    while (node != NULL) {
      AdjVNode* temp = node;
      node = node->next;
      free(temp);
    }
  }
  free(G);
}

void printGraph(Graph* G) {
  for (int i = 0; i < G->nv; i++) {
    AdjVNode* node = G->adjList[i].first;
    if (node == NULL) {
      continue;
    }
    printf("顶点%d的邻接表:", i);
    while (node != NULL) {
      printf("->%d(%d)", node->v, node->weight);
      node = node->next;
    }
    printf("\n");
  }
}

/// @brief 在图中插入一条有向边
/// @param G 图
/// @param E 边
/// @return 是否插入成功
static bool InsetEdge(Graph* G, const Edge* const E) {
  int v = E->v;
  AdjVNode* node = (AdjVNode*)malloc(sizeof(AdjVNode));
  if (node == NULL) {
    printf("内存分配失败\n");
    return false;
  }
  node->v = v;
  node->weight = E->weight;
  node->next = G->adjList[E->u].first;
  G->adjList[E->u].first = node;
  return true;
}

/// @brief Dijkstra算法，求最短路径
/// @param G 图
/// @param dist 存储最短路径的数组，其值会被修改
/// @param path 存储路径的数组，其值会被修改
/// @param s 起点
/// @param target 目标点 
/// @return 是否找到了目标点
/// @note dist和path数组的长度应该大于等于顶点数的最大值
/// @note dist数组存储的是起点到每个顶点的最短路径
/// @note path数组存储的是规划出来的路线该顶点的前一个顶点，如果前面没有顶点了，那么该顶点的前一个顶点为-1
/// @note 如果找到了目标点，就会停止，此时的dist和path数组只能表示到目标点的最短路径，dist数组中的其他值不一定是最短路径
bool Dijkstra(const Graph* G, int dist[], int path[],const int s,const int target) {
  // 创建一个最小堆
  MinHeap* heap = createMinHeap(G->nv);
  // 创建一个布尔数组，用于记录每个顶点是否在堆中
  bool* tag = (bool*)calloc(G->nv, sizeof(bool));
  // 如果堆或布尔数组的创建失败，打印错误信息并返回false
  if (heap == NULL || tag == NULL) {
    printf("内存分配失败\n");
    return false;
  }

  // 初始化dist和path数组
  for (int i = 0; i < G->nv; i++) {
    dist[i] = INF;  // 无穷大
    path[i] = -1;   // -1表示无路径
  }
  AdjVNode* node = G->adjList[s].first;
  while (node) {
    dist[node->v] = node->weight;
    path[node->v] = s;
    node = node->next;
  }
  dist[s] = 0;    // 起点到自己的距离为0
  tag[s] = true;  // 起点已访问
  // 将除了起点之外的所有顶点到起点的距离插入到堆中
  for (int i = 0; i < G->nv; i++) {
    if (i == s) {
      continue;
    }
    insertIndex(heap, dist, i);
  }

  // 找到目标点或者堆为空
  while (heap->size > 0 && tag[target] == false) {
    /*找出与T集合(未找到最短路径的顶点的集合)中到源点距离最短的点，加入U集合中*/
    int u = deleteMin(heap, dist);
    if (dist[u] >= INF) {
      break;
    }
    tag[u] = true;  // 标记为已访问

    /*T集合中所有的点的最短路径与经过u点的最短路径进行比较*/
    node = G->adjList[u].first;
    while (node != NULL) {
      if (tag[node->v] == false) {  // 如果顶点v未被访问，即在T集合中
        int v = node->v;
        if (isFindInMap==NULL || isFindInMap(path[u], u, v) == true) {//确保这条路是在地图上的
          int weight = node->weight;
          if (dist[u] + weight < dist[v]) {//如果经过u点的路径比原来的路径短
            fix_up(heap, dist, v, dist[u] + weight);//更新最短路径数组中的值
            path[v] = u;//更新path路径数组中的值
          }
        }
      }
      node = node->next;
    }
  }
  deleteMinHeap(heap);
  free(tag);
  // 如果找到了目标点，返回true
  if (tag[target] == false)
    return false;
  else
    return true;
}

// static bool isFindInMap(int now, int next, int nNext) {
//   typedef struct map_linkInforTypeDef {
//   int nextNode;   // 下一个节点
//   int nNextNode;  // 下下一个节点
// } map_linkInforTypeDef;
//   extern const map_linkInforTypeDef mapInformation[][15];
//   const map_linkInforTypeDef* map_linkInfor = mapInformation[now];
//   for (int i = 0; i < 15; i++) {
//     if (map_linkInfor[i].nextNode == next && map_linkInfor[i].nNextNode == nNext) {
//       return true;
//     }
//   }
//   return false;
// }
/**
 * @brief 获取路径
 * 
 * @param path dijkstra算法中的path数组
 * @param v 目标点
 * @param way 存储路径的数组
 * @param wayMaxLen 存储路径的数组的最大长度
 */
void getWay(int path[], int v, uint8_t way[], int wayMaxLen) {
  int reverseWay[wayMaxLen];
  int i = 0;
  while (v != -1) {
    reverseWay[i] = v;
    v = path[v];
    i++;
  }
  for (int j = 0; j < i; j++) {
    way[j] = reverseWay[i - j - 1];
  }
  way[i] = 0;
}
//示例
// int main1() {
//   Graph* G = createGraph(gl_edges, sizeof(gl_edges) / sizeof(Edge));
//   printGraph(G);
//   int dist[MAX_VERTEXES];
//   int path[MAX_VERTEXES];
//   Dijkstra(G, dist, path, 1,7);
//   int way[MAX_VERTEXES];
//   getWay(path, 7, way, MAX_VERTEXES);
//   for (int i = 0; i < MAX_VERTEXES; i++) {
//     if (way[i] == 0) {
//       break;
//     }
//     printf("%d->", way[i]);
//   }
//   deleteGraph(G);
//   return 0;
// }